package 链表;

/**
 * 给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
 */
public class 链表中环的入口节点 {

    public static void main(String[] args) {
    }

    /**
     * 两个指针分别从链表头和相遇点继续出发，每次走一步最后一定在入口相遇
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {


        if (head == null || head.next == null || head.next.next == null ){
            return null;
        }

        ListNode fast = head;
        ListNode slow = head;


        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                break;
            }

        }
        if (fast == slow){

            while(head != slow){
                head = head.next;
                slow = slow.next;
            }
            return slow;
        }else{
            return null;
        }
    }


}
